package org.example;

import java.util.Arrays;

public class Test4 {
    //leetcode 435 无重叠区间 https://leetcode.cn/problems/non-overlapping-intervals/description/

    /**
     * 如何判断有重叠区间呢，就是判断intervals[n][0]与end的关系，如果intervals[i][0]<end，就说明有重叠区间
     * 如果有重叠区间，那么删除n-1区间还是n区间才能保证删除次数最少呢，
     * 因为判断是否有重叠区间的判断条件是intervals[i][0]是否小于end，那么保证删除次数最少的话
     * 那就是保证end局部最小，所以就按照区间的末作为标准进行升序排列
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a, b) -> {
            return a[1] - b[1];
        });
        int end = intervals[0][1];
        int ans = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                ans++;
            }else end = intervals[i][1];
        }
        return ans;
    }

    public static void main(String[] args) {
        Test4 test4 = new Test4();
        int[][] arr = {{0,2},{1,3},{2,4},{3,5},{4,6}};
        test4.eraseOverlapIntervals(arr);
        System.out.println(777);
    }
}
